package com.sjb.training.lc;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: 有点儿意思
 * @Description:
 */
public class Test {

    public static void main(String[] args) {
        int[] nums = {55,58,5,6,56,74,16};
        quickSort(nums,0,nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }


    static void quickSort(int[] nums,int l ,int r){
        if (l >= r){
            return;
        }

        int pivot = partition(nums,l,r);
        quickSort(nums,l,pivot - 1);
        quickSort(nums,pivot + 1, r);
    }


    /**
     * 分区函数
     * @param nums
     * @param l
     * @param r
     * @return
     */
    static int partition(int[] nums,int l ,int r){
        // 获取随机数
        Random random = new Random();
        int pivot = l +  random.nextInt(r - l + 1);
        swap(nums,pivot,l);
        // 双指针
        int i = l + 1;
        int j = r;

        while (i<=j){
            while(i <= j && nums[i] <= nums[l]){
                i++;
            }
            while (i <= j && nums[j] >= nums[l]){
                j--;
            }
            if (i < j){
                swap(nums,i, j);
            }
        }
        swap(nums,l,j);
        return j;
    }


    static void swap(int[] nums,int i ,int j){
        int temp =nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
